#include<iostream>
#include<vector>
#include<stack>
using namespace std;
/** Definition for a binary tree node. */
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution {
public:
    stack<TreeNode*> Stack;
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        TreeNode* root = new TreeNode(preorder[0]);
        Stack.push(root);  //第一个元素入栈
        int index = 0;  //指向inorder的第一个元素，如果不和栈顶相同，说明当前节点为左孩子
        for(int i=1;i<preorder.size();i++) {
            TreeNode* topNode = Stack.top();
            if(topNode->val!=inorder[index]){  //说明当前一个preorder[i]为栈顶的左孩子
                TreeNode* node = new TreeNode(preorder[i]);
                topNode->left = node;
                Stack.push(node);   //并且将当前节点入栈
            }else{  //若不是，则当前节点为已在栈中的某个元素的右孩子
                //遍历栈内现有元素，直到找到这个“某个元素”，并将preorder[i]置为其右孩子
                TreeNode* findNode = nullptr;
                while(Stack.empty()==false && Stack.top()->val == inorder[index]){
                    index++;
                    findNode = Stack.top();
                    Stack.pop();
                }
                if(findNode!=nullptr){
                    TreeNode* node = new TreeNode(preorder[i]);
                    findNode->right = node;
                    Stack.push(node);
                }
            }
        }
        return root;
    }
};
int main(int argc, char* argv[]) {
    vector<int>pre={3,9,20,15,7};
    vector<int>inorder={9,3,15,20,7};
    Solution solution = Solution();
    solution.buildTree(pre,inorder);
}